package com.yohann.algorithm;

import java.util.Date;

/**
 * <p>
 * 排序算法
 * 1.插入排序
 * 2.选择排序
 * 3.交换排序
 * 4.归并排序
 * 5.基数排序
 * </p>
 *
 * @author Yohann
 * @since 2020/9/24
 */
public class SortTest {
    public static void main(String[] args) {
        //测试冒泡排序
//        int[] arr = new int[]{1, 6, 3, -1, 10, 0};
//        int[] ints = bubbleSort(arr);
//        int[] ints = selectSort(arr);
//        int[] ints = insertionSort2(arr);
//        for (int i = 0; i < arr.length; i++) {
//            System.out.println(ints[i]);
//        }

        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int) (Math.random() * 8000000);
        }

        int[] ints = new int[80000];
        for (int i = 0; i < 80000; i++) {
            ints[i] = arr[i];
        }

        int[] ints2 = new int[80000];
        for (int i = 0; i < 80000; i++) {
            ints2[i] = arr[i];
        }

        int[] ints3 = new int[80000];
        for (int i = 0; i < 80000; i++) {
            ints3[i] = arr[i];
        }

        long time = System.currentTimeMillis();
        insertionSort(arr);
        System.out.println(System.currentTimeMillis() - time);

        long time2 = System.currentTimeMillis();
        insertionSort2(ints);
        System.out.println(System.currentTimeMillis() - time2);

        long time3 = System.currentTimeMillis();
        bubbleSort(ints2);
        System.out.println(System.currentTimeMillis() - time3);

        long time4 = System.currentTimeMillis();
        selectSort(ints3);
        System.out.println(System.currentTimeMillis() - time4);
    }

    /**
     * 冒泡排序
     * 逐个与相邻的数比较 大于右侧则交换
     * @param arr
     * @return
     */
    public static int[] bubbleSort(int[] arr) {
        int temp = 0;
        boolean flag = false;

        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    flag = true;
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }

            //检测有没有变化顺序
            if (flag == false) {
                break;
            } else {
                flag = false;
            }
        }

        return arr;
    }

    /**
     * 选择排序
     * 将未排序的最小的排到未排序部分最前面
     * @param arr
     * @return
     */
    public static int[] selectSort(int[] arr) {
        int minIndex = 0;
        int min = 0;

        for (int i = 0; i < arr.length - 1; i++) {
            //第i个与后面的比较大小 获取比自身小的值以及索引
            for (int j = 1 + i; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    min = arr[j];
                    minIndex = j;
                }
            }

            //最小值索引变化 两个数互换
            if (minIndex != i) {
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
        }

        return arr;
    }

    //插入排序
    public static int[] insertionSort(int[] arr) {
        int index = 0;
        int current = 0;

        //从第二个开始逐个与已排序的比较
        for (int i = 1; i < arr.length; i++) {
            current = arr[i];
            for (int j = i - 1; j >= 0; j--) {
                //当已排序的数大于该数 则在该处插入
                if (arr[j] > arr[i]) {
                    arr[j + 1] = arr[j];
                    index = j;
                }
            }
            if (index > 0){
                arr[index - 1] = current;
            }
            else{
                arr[0] = current;
            }
        }

        return arr;
    }

    /**
     * 插入排序
     * 将需要排序的往左移动 并比较大小 找到合适位置
     * 将合适位置后面的已排序部分往后移动
     * @param arr
     * @return
     */
    public static int[] insertionSort2(int[] arr) {
        int insertValue;
        int insertIndex;

        for (int i = 1; i < arr.length; i++) {
            //需要插入的值
            insertValue = arr[i];
            //比较的索引 即前一个位置的索引
            insertIndex = i - 1;

            //如果还没到达最前面 并且 插入值小于前一个值 前一个值往后移动
            while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }

            //插入数据
            arr[insertIndex + 1] = insertValue;
        }

        return arr;
    }
}